package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/19 7:45 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1110 {

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {

        List<TreeNode> result = new LinkedList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        result.add(root);
        Set<Integer> set = new HashSet<>();

        for (int delete : to_delete) {
            set.add(delete);
        }

        while (!deque.isEmpty()) {
            TreeNode cur = deque.poll();
            if (set.contains(cur.val)) {
                result.remove(cur);
                if (cur.left != null) {
                    result.add(cur.left);
                }
                if (cur.right != null) {
                    result.add(cur.right);
                }
            }

            if (cur.left != null) {
                deque.offer(cur.left);
                if (set.contains(cur.left.val)) {
                    cur.left = null;
                }
            }
            if (cur.right != null) {
                deque.offer(cur.right);
                if (set.contains(cur.right.val)) {
                    cur.right = null;
                }
            }
        }
        return result;
    }
}
